Estoy abordando este problema y parece que no puedo llegar a la solución correcta. La pregunta es:
"Dada una lista de n enteros arr[0..(n-1)], determina el número de diferentes pares de elementos dentro de ella que suman k. Si un entero aparece en la lista varias veces, cada copia se considera diferentes; es decir, dos pares se consideran diferentes si un par incluye al menos un índice de matriz que el otro no incluye, incluso si incluyen los mismos valores.
Mi enfoque es que estoy construyendo un mapa que contiene cada número en la matriz y la cantidad de veces que ocurre. Luego itero sobre el mapa para encontrar mi respuesta.
function numberOfWays(arr, k) { let output = 0; let map = {}; // put values and # of occurences into map for(let i = 0; i < arr.length; i++) { let key = arr[i]; if(!(key in map)) { map[key] = 1; } else { map[key]++; } } for(let key in map) { let difference = k-key if((difference) in map) { if(k/2 === key) { output += map[key]*(map[key]-1)/2; } else { output += map[key] * map[key] / 2; // divide by 2 so that pairs aren't counted twice } } } return output; }Los dos casos de prueba son:
var arr_1 = [1, 2, 3, 4, 3]; resultado esperado: [2] -- Obtengo [3]
var arr_2 = [1, 5, 3, 3, 3]; resultado esperado: [4] -- Obtengo [5.5]
Definitivamente estoy haciendo algo mal en mis cálculos, pero parece que no puedo entenderlo.
Esta es una forma de anidar los bucles para encontrar los pares en el arreglo "arr" con la suma "k".
function numberOfWays(arr, k) { let output = 0; for (i = 0; i < arr.length; i++) { for (n = i+1; n < arr.length; n++) { if (arr[i] + arr[n] == k) output++; } } return output; } function numberOfWays(items, k) { // Clone as to not mutate original array const arr = [...items] let count = 0 // Stop comparing when no items left to compare while (arr.length) { for (let i = 0; i < arr.length; i++) { // Compare each item to the first item const sum = arr[0] + arr[i + 1] if (sum === k) { count++ } } // Remove the first item after comparing to the others arr.shift() } return count } console.log(numberOfWays([1, 2, 3, 4, 3], 6)) console.log(numberOfWays([1, 5, 3, 3, 3], 6)) console.log(numberOfWays([1, 1, 1, 1, 1], 2))Puede contar los valores más pequeños y más grandes para construir k y luego tomar el producto o, si solo dos del mismo valor están construyendo la suma, tomar el factorial de la cuenta dividida por dos.
function numberOfWays(array, k) { const f = n => +!n || n * f(n - 1), pairs = {}; for (const value of array) { const smaller = Math.min(value, k - value); pairs[smaller] ??= { one: 2 * smaller === k, min: 0, max: 0 }; pairs[smaller][value === smaller ? 'min' : 'max']++; } let count = 0; for (const k in pairs) { const { one, min, max } = pairs[k]; if (one) { if (min > 1) count += f(min) / 2; } else if (min && max) { count += min * max; } } return count; } console.log(numberOfWays([1, 2, 3, 4, 3], 6)); // 2 console.log(numberOfWays([1, 5, 3, 3, 3], 6)); // 4